// hard

// 给定一个字符串s和一个字符模式串p
// 要求：实现一个支持'.'和'*'的正则表达式匹配，两字字符串完全匹配才算匹配成功，如果匹配成功，则返回true，否则返回false
// . 匹配任意单个字符
// * 匹配0或者多个前面的那一个元素

// 解题思路： 动态规划
// 1. 划分阶段，按照两个字符串的结尾位置进行阶段划分
// 2. 定义状态， 定义dp[i][j]表示为：字符串s的前i个字符与字符串p的前j个字符是否匹配
// 3. 状态转移方程
//      1. 如果s[i-1] == p[j-1],则s的第i个字符与p的第j个字符是匹配的，此时dp[i][j] = dp[i-1]dp[j-1]
//      2. 如果p[j-1] == '.',则s的第i个字符与p的第j个字符时匹配的，此时dp[i][j] = dp[i-1]dp[j-1]
//      3. 如果p[j-1] == '*',则我们可以对字符p[j-2]进行0~若干次的匹配
//          1. 如果s[i-1] != p[j-2] 并且p[j-2] != '.',则说明当前*匹配不上，只能匹配0次，则s的前i个字符与p的前j个字符是否匹配取决于字符串s的前i个字符与p的前j-2个字符是否匹配
//          即dp[i][j] = dp[i][j-2]
//          2. 如果s[i-1] == p[j-2]，或者p[j-2] == '.',则说明当前*前面的字符p[j-2]可以匹配s[i-1]
//              1. 如果匹配0个，则dp[i][j] = dp[i][j-2]
//              2. 如果匹配1个，dp[i][j] = dp[i][j-1]
//              3. 如果匹配多个，则dp[i][j] = dp[i-1][j]
// 4. 初始条件
//      1. 默认状态下，两个空字符串时匹配的，即dp[0][0] = true
//      2. 当s为空，p右端有*时，想要匹配，如果空字符串与 去掉p右端的*和*前面的字符之后的字符串匹配的话，则空字符串与p匹配，dp[0][j] = dp[0][j-2]
// 5. 最终结果
// dp[i][j]表示为：s的前i个字符与p的前j个字符是否匹配，则最终结果为dp[size_s][size_p],其中size_s是s的长度，size_p是p的长度

// 复杂度分析
// 时间复杂度：O(mn)
// 空间复杂度：O(mn)


function isMatch(s, p) {
    let size_s = s.length
    let size_p = p.length
    let dp = new Array(size_s + 1).fill(0).map(() => new Array(size_p + 1).fill(false))
    dp[0][0] = true

    for (let j = 1; j < size_p + 1; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2]
        }
    }
    for (let i = 1; i < size_s + 1; i++) {
        for (let j = 1; j < size_p + 1; j++) {
            if (s[i - 1] === p[j - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1]
            } else if (p[j - 1] === '*') {
                if (s[i - 1] !== p[j - 2] && p[j - 2] !== '.') {
                    dp[i][j] = dp[i][j - 2]
                } else {
                    dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j]
                }
            }
        }
    }
    return dp[size_s][size_p]
}

let s = "cab", p = ".*"
console.log(isMatch(s, p));